#ifndef GRAPHTEMPLATEUTILS_H_
#define GRAPHTEMPLATEUTILS_H_

#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>

#include <boost/optional.hpp>
#include <boost/bind.hpp>


namespace GRAPH_SUPPORT_NS
{
namespace utils
{

/**
 * returns found optional 4 GraphT::GrEdgePtr if at least one exists and
 * false otherwise. if multiple edges: beg -> end exist, optional 4 any
 * edge would be returned.
 */
template< typename GraphT >
boost::optional< typename GraphT::GrEdgePtr > findEdge(
		GraphT & gr,
		const typename GraphT::GrVertex & beg,
		const typename GraphT::GrVertex & end
)
{
	typedef typename GraphT::GrEdge GrEdge;
	typedef typename GraphT::GrEdgePtr GrEdgePtr;
	typedef typename GraphT::EdgeIterator EdgeIterator;
	typedef boost::optional< typename GraphT::GrEdgePtr > GrEdgeOptional;

	size_t begVid = gr.vert2num( beg );
	size_t endVid = gr.vert2num( end );
	/**
	 * the implementation is sophisticated, see the first doc in graph_support/Graph.h for details.
	 */
	typename GraphT::EdgeIterator fiter =
			std::find_if( gr.getEdgsBegId( begVid ), gr.getEdgsEndId( begVid ),
					boost::bind< bool >( std::equal_to< size_t >(), endVid,
							boost::bind( & GrEdge::endId,
									boost::bind( ptr2ref< GrEdge, GrEdgePtr > , _1 ) ) ) );
	return fiter != gr.getEdgsEndId( begVid ) ?
			GrEdgeOptional( * fiter ) :
			GrEdgeOptional();
}

/**
 * pushbacks all edge pointers which lead: beg -> end
 */
template< typename GraphT >
void findEdges(
		GraphT & gr,
		const typename GraphT::GrVertex & beg,
		const typename GraphT::GrVertex & end,
		std::vector< typename GraphT::GrEdgePtr > & output,
		bool clearOutputBeforeSearch = true
)
{
	typedef typename GraphT::EdgeIterator EdgeIterator;
	typedef typename GraphT::GrEdgePtr GrEdgePtr;

	if ( clearOutputBeforeSearch )
	{
		output.clear();
	}

	size_t begVid = gr.vert2num( beg );
	size_t endVid = gr.vert2num( end );

	EdgeIterator stopit = gr.getEdgsEndId( begVid );
	for ( EdgeIterator it = gr.getEdgsBegId( begVid ); it != stopit; ++it )
	{
		// TODO: try: GrEdge & e = * * it;
		GrEdgePtr eptr = * it;
		// TODO: try:
//		GrEdge & e = * eptr;
//		if ( e.beg() == beg && e.end() == end )
		if ( eptr->begId() == begVid && eptr->endId() == endVid )
		{
			output.push_back( eptr );
		}
	}
}

template< typename GraphT >
typename GraphT::EdgeAttributes::Capacity getFlow(
		GraphT & gr,
		typename GraphT::GrVertex beg,
		typename GraphT::GrVertex end
)
{
	typedef typename GraphT::GrEdge GrEdge;
	typedef typename GraphT::GrEdgePtr GrEdgePtr;
	typedef typename GraphT::EdgeAttributes EdgeAttributes;
	typedef typename EdgeAttributes::Capacity Capacity;

	std::vector< GrEdgePtr > buf;
	findEdges( gr, beg, end, buf );
	Capacity result = std::accumulate( buf.begin(), buf.end(), ( Capacity ) 0,
			boost::bind( std::plus< Capacity >(), _1,
					boost::bind( & EdgeAttributes::getFlow, boost::bind( & GrEdge::getAttributes,
							boost::bind( & utils::ptr2ref< GrEdge, GrEdgePtr >, _2 ) ) ) ) );
	return result;
}

}
}

#endif /* GRAPHTEMPLATEUTILS_H_ */
